//
//  graphCalc.m
//  ElektroM
//
//  Created by Michael on 16.11.09.
//  Copyright 2009 Artgruppe inc. All rights reserved.
//

#import "graphCalc.h"
#import "Constants.h"

@implementation graphCalc

-(void) init
{
    _parents = (int*) malloc(sizeof(int)*[_aiNodes count]);
    _weights = (int*) malloc(sizeof(int)*[_aiNodes count]);
}

-(void) cleanUp
{
    if(_aiNodes!=nil)
	[_aiNodes release];
    _aiNodes=nil;

    if(_aiLineNumbers!=nil)
	[_aiLineNumbers release];
    _aiLineNumbers=nil;

    free(_parents);
    free(_weights);
}

-(void) setNodes: (NSArray*) aiNodes
{
    _aiNodes=aiNodes;
    [_aiNodes retain];
}

-(void) setLineNumbers: (NSArray*) aiLineNumbers
{
    _aiLineNumbers=aiLineNumbers;
    [_aiLineNumbers retain];
}

-(int) getParent: (int)node
{
    return _parents[node];
}

-(int) getWeight: (int)node
{
    return _weights[node];
}

-(void) setStart: (int)nStart
{
    _nStart=nStart;

    for(int i=0; i<[_aiNodes count]; i++)
	_weights[i]=Infinity;

    _weights[nStart]=0;
}

-(void) printWeights
{
    for(int i=0; i<[_aiNodes count]; i++)
	printf("%d weight: %d\n", i, _weights[i]);

}

-(void) applyCyclon
{
    int nCurLine=[[_aiLineNumbers objectAtIndex: _nStart] intValue];

    NSMutableArray* anNumbersNextToUse=[NSMutableArray arrayWithCapacity: 25];
    NSMutableArray* anCurLineNodeNumbers=[NSMutableArray arrayWithCapacity: 25];
    NSMutableArray* knotsWhereIveBeen=[NSMutableArray arrayWithCapacity: [_aiNodes count]];

    int nCurNode=_nStart;

    for(;;)
    {
	for(int i=0; i<[[_aiNodes objectAtIndex: nCurNode] count]; i++)
	{
	    int nNode=[[[[_aiNodes objectAtIndex: nCurNode] objectAtIndex: i] objectForKey: kKnot] 
		intValue];

	    // added for correspondence between line numbers and nodes;
	    // tricky place:)
	    if(nNode==-1)
		continue;
	    int nWeight=[[[[_aiNodes objectAtIndex: nCurNode] objectAtIndex: i] objectForKey: kWeight] 
		intValue];

	    // relax the node:
	    //[self relax: nCurNode withNode: nNode withWeight: nWeight];
	    [self relax: nNode withNode: nCurNode withWeight: nWeight];

	    if([[_aiLineNumbers objectAtIndex: nNode] intValue] == nCurLine)
	    {
		// add the node to the queue for next proceeding:
		[anCurLineNodeNumbers addObject: [NSNumber numberWithInt:nNode]];
	    }
	    else
	    {
		// else add the node to another queue for other lines
		[anNumbersNextToUse addObject: [NSNumber numberWithInt: nNode]];
	    }
	}

	[knotsWhereIveBeen addObject: [NSNumber numberWithInt: nCurNode]];

	// if we've got more elements to proceed on the current line
	// dequeue it:
	bool bFound;
	do{
	    bFound=false;
	    if([anCurLineNodeNumbers count]==0)
		break;
	    nCurNode=[[anCurLineNodeNumbers objectAtIndex: 0] intValue];
	    [anCurLineNodeNumbers removeObjectAtIndex: 0];
	    bFound=true;
	}
	while([knotsWhereIveBeen containsObject: [NSNumber numberWithInt: nCurNode]]); // we've been there before..

	// change current line:
	if(!bFound)
	{
	    // try to find another node on the other line, where we were not:
	    do{
		bFound=false;
		if([anNumbersNextToUse count]==0)
		    break;
		nCurNode=[[anNumbersNextToUse objectAtIndex: 0] intValue];
		[anNumbersNextToUse removeObjectAtIndex: 0];
		bFound=true;
	    }
	    while([knotsWhereIveBeen containsObject: [NSNumber numberWithInt: nCurNode]]); // we've been there before..
	    // we've not been there, use that line
	    if(bFound)
		nCurLine=[[_aiLineNumbers objectAtIndex: nCurNode] intValue];
	    else
		break; // there are no more lines, where we were not.
	    // exit...
	}
    }
}

-(void) applyCyclonC: (int*)allowedLineNumbers withAllowedCount:(int)nAllowedCount
{
	[self setStart: _nStart];
    
	int nCurLine=[[_aiLineNumbers objectAtIndex: _nStart] intValue];
	
    NSMutableArray* anNumbersNextToUse=[NSMutableArray arrayWithCapacity: 25];
    NSMutableArray* anCurLineNodeNumbers=[NSMutableArray arrayWithCapacity: 25];
    NSMutableArray* knotsWhereIveBeen=[NSMutableArray arrayWithCapacity: [_aiNodes count]];
	
    int nCurNode=_nStart;
	
    for(;;)
    {
		for(int i=0; i<[[_aiNodes objectAtIndex: nCurNode] count]; i++)
		{
			int nNode=[[[[_aiNodes objectAtIndex: nCurNode] objectAtIndex: i] objectForKey: kKnot] 
					   intValue];
			
			// added for correspondence between line numbers and nodes;
			// tricky place:)
			if(nNode==-1)
				continue;
			int nWeight=[[[[_aiNodes objectAtIndex: nCurNode] objectAtIndex: i] objectForKey: kWeight] 
						 intValue];
			
			// relax the node:
			//[self relax: nCurNode withNode: nNode withWeight: nWeight];
			[self relax: nNode withNode: nCurNode withWeight: nWeight];
			
			if([[_aiLineNumbers objectAtIndex: nNode] intValue] == nCurLine)
			{
				// add the node to the queue for next proceeding:
				[anCurLineNodeNumbers addObject: [NSNumber numberWithInt:nNode]];
			}
			else
			{
				// else add the node to another queue for other lines
				[anNumbersNextToUse addObject: [NSNumber numberWithInt: nNode]];
			}
		}
		
		[knotsWhereIveBeen addObject: [NSNumber numberWithInt: nCurNode]];
		
		// if we've got more elements to proceed on the current line
		// dequeue it:
		bool bFound;
		do{
			bFound=false;
			if([anCurLineNodeNumbers count]==0)
				break;
			nCurNode=[[anCurLineNodeNumbers objectAtIndex: 0] intValue];
			[anCurLineNodeNumbers removeObjectAtIndex: 0];
			bFound=true;
		}
		while([knotsWhereIveBeen containsObject: [NSNumber numberWithInt: nCurNode]]); // we've been there before..
		
		// change current line:
		if(!bFound)
		{
			// try to find another node on the other line, where we were not:
			do{
				bFound=false;
				if([anNumbersNextToUse count]==0)
					break;
				nCurNode=[[anNumbersNextToUse objectAtIndex: 0] intValue];
				[anNumbersNextToUse removeObjectAtIndex: 0];
				bool bAllowed=false;
				for(int j=0; j<nAllowedCount; j++)
					if(allowedLineNumbers[j]==[[_aiLineNumbers objectAtIndex:nCurNode] intValue])
						bAllowed=true;				
				
				if(!bAllowed){
					// set the node from the used list:
					nCurNode=[[knotsWhereIveBeen objectAtIndex:0] intValue];
					continue; // the node shouldn't be used!
				}			
				
				bFound=true;
			}
			while([knotsWhereIveBeen containsObject: [NSNumber numberWithInt: nCurNode]]); // we've been there before..
			// we've not been there, use that line
			if(bFound)
				nCurLine=[[_aiLineNumbers objectAtIndex: nCurNode] intValue];
			else
				break; // there are no more lines, where we were not.
			// exit...
		}
    }
}

-(void) relax: (int)nRelaxing withNode:(int)nFrom withWeight:(int)nWeight
{
	//printf("relax's weight %d; new one %d\n", _weights[nRelaxing], _weights[nFrom]+nWeight);
    if(_weights[nRelaxing] > _weights[nFrom]+nWeight)
    {
	_parents[nRelaxing]=nFrom;
	_weights[nRelaxing]=_weights[nFrom]+nWeight;
    }
}
@end
